1. Field of the Invention
The present invention generally relates to mobile transmitter position monitoring and locating systems and, more particularly, to a transmitter location searching system which uses a search algorithm based on geographical partition and local optimization.
2. Description of the Prior Art
There are many applications for mobile transmitter position monitoring and locating systems. For example, transmitters may be fitted to motor vehicles in an urban and/or suburban environment so that the positions of the vehicles may be monitored by one or more base stations. The vehicles may be governmental vehicles, such as police automobiles or fire and rescue trucks, or they may be commercial vehicles, such as delivery trucks or service vehicles. Alternatively, the transmitters may be mounted on ships or other mobile vessels to enable their positions to be monitored through use of satellites. The latter system, as described in R. E. Anderson U.S. Pat. No. 4,161,734, issued Jul. 17, 1979 and assigned to the instant assignee, employs an active ranging satellite and a satellite that transmits timing signals. One line of position is determined by two-way active ranging through the first satellite and the other line of position is determined by one-way ranging from the second satellite. The time interval between arrival of a timing signal and reception of the active ranging signal, measured at the ship, is sent to an earth station where the position fix is computed. The Anderson U.S. Pat. No. 4,161,734 is incorporated herein by reference.
A typical vehicle monitoring system includes, in addition to the transmitters fitted to the vehicles, a plurality of base stations distributed in the geographical area over which the monitoring takes place. A transmitter on a vehicle transmits, either periodically or in response to a polling signal, a short radio signal which is propagated in an urban and/or suburban multipath fading environment and received by each base station. Using signal arrival times measured at each base station, the location system must estimate the location of the mobile transmitter.
The transmitter location searching problem can be formulated as an optimization problem. An individual cost function for each base station is constructed as follows: ##EQU1## where the left-hand term is the individual cost function for the i'th base station, c is the speed of light, t.sub.i is the measured signal arrival time at the i'th base station, x.sub.i and y.sub.i are the known geographical coordinates of the i'th base station, t is the time when the radio signal is transmitted, and x and y are the geographical coordinates of the mobile transmitter to be located. As is well known in the art, the term "cost" employed herein refers to the error associated with each measurement. Intuitively, the individual cost function for each base station represents the difference between the radio propagation distance and the physical distance between the base station and the estimated transmitter location.
For the case shown in FIG. 1, a total cost function is constructed from the six individual cost functions by summing the weighted square of all the individual cost functions as follows: ##EQU2## where w.sub.i is a weighting factor (0.+-.w.sub.i .+-.1) which is associated with the signal strength measured at each base station. For a strong signal, w.sub.i is given a value close to one, and for a weak signal, it is given a value close to zero. The problem of finding the location of the transmitter is now transformed to the problem of finding the triple (x,y,t) which minimizes the total cost function; i.e., solve ##EQU3##
Because of the nonlinearity involved in equation (1), equation (3) is difficult to solve. In order to simplify the problem, George L. Turin, William S. Jewell and Tom L. Johnson ("Simulation of Urban Vehicle-Monitoring Systems", IEEE Transactions on Vehicular Technology, Vol. VT-21, No. 1, Feb. 1972, at pages 9 to 16, and incorporated herein by reference) linearized equation (1) by means of a first order Taylor series expansion around a candidate triplet (x.sub.0,y.sub.0,t.sub.0) before equation (1) is substituted into equation (2). The result is as follows: ##EQU4## where some changes of variables have been made and x.sub.0,y.sub.0,t.sub.0 is the initial guess of the vehicle's location. The relations between old and new variables are given in equations (5), (6) and (7) as follows: ##EQU5##
Because equation (5) is linear, the point (x.sub.m,y.sub.m,t.sub.m) which produces a minimum in equation (4) is the simultaneous solution of the following three partial derivative equations: ##EQU6## These three equations in {h,k,u} are linear, and can be solved by the well-known Gaussian elimination method.
After equation (8) is solved, the candidate point is modified according to the following equations: ##EQU7## The modified candidate point (x.sub.0,y.sub.0,t.sub.0) is substituted into equation (4), and the algorithm is iterated until the sum of the magnitudes of h, k and cu is below a selected threshold. Generally speaking, the algorithm employed by Turin et al. converges quickly. Unfortunately, this algorithm does not indicate how to find a reliable initial candidate point (x.sub.0,y.sub.0,t.sub.0). By computer simulation, we have found that the convergence of this algorithm is affected by the initial candidate point, the location of the transmitter, and the uncertainty in the signal arrival times (due primarily to the multipath propagation effects in urban and suburban areas). In fact, algorithm convergence may sometimes not occur due to selecting a bad initial candidate point and poor channel conditions.